<!DOCTYPE html>
<meta charset="utf-8">
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script>
  MathJax.Hub.Config({
                      tex2jax: {inlineMath: [['$', '$'], ['\\(','\\)']]},
                      TeX: { equationNumbers: {autoNumber: "AMS"} },
                      "HTML-CSS": { showMathMenu: false,
                                    scale: 90 }

                     });
</script>
<link rel="stylesheet" href="http://yui.yahooapis.com/pure/0.4.2/pure-min.css">
<style>
@import url(http://fonts.googleapis.com/css?family=PT+Serif|PT+Serif:b|PT+Serif:i|PT+Sans|PT+Sans:b);
@import url(http://fonts.googleapis.com/css?family=Lato);
html {
   min-width: 1040px;
}

body {
   background: #fcfcfa;
   color: #333;
   font-family: "PT Serif", serif;
   /*margin: 0 1em 4em auto;*/
   position: relative;
   width: 960px;
   left: 13em;
}

h1, h2, h3, h4 { font-family: "Lato", "PT Serif", serif; color: #000; text-rendering: optimizeLegibility; }

h1 {
  font-size: 64px;
  line-height: 73px;
  font-weight: 900;
  margin-top: 0.67em;
  margin-right: 0;
  margin-bottom: 0;
  margin-left: 0;
}

h2 {
   margin-top: 2em;
}

subtitle {
   display:block;
   font-family: "PT Serif", serif;
   font-size: 32px;
   font-style: italic;
   font-weight: 100;
}

p {
  line-height: 150%;
  width: 720px;
}

a {
  color: steelblue;
  cursor: auto;
}

a:not(:hover) {
   text-decoration: none;
}

pre {
   border-left: solid 2px #ccc;
   padding-left: 18px;
   margin: 2em 0 2em -20px;
}

aside {
   font-size: small;
   right: 0;
   position: absolute;
   width: 180px;
}

#nav {
        left: 5px;
        font-family: "Lato", serif;
        font-weight: 700;
        list-style: none;
        margin: 0;
        position: fixed;
        top: 10px;
        box-sizing: border-box;
}


#nav li {
        margin-bottom: 0px;
}

#nav a {
        color: #333;
        display: block;
        font-size: 14px;
        border-left: 3px solid #fcfcfa;
        padding: 5px 10px;
        text-decoration: none;
}

#nav a:hover {
   border-left: 3px solid steelblue;
}

#nav .current a {
   border-left: 3px solid steelblue;
}

rect {
  fill: none;
  pointer-events: all;
}

.node {
  fill: #000;
}

.cursor {
  fill: none;
  stroke: brown;
  pointer-events: none;
}

.link {
  stroke: #999;
}

</style>
<body>
  <ul id="nav">
    <li class="current"><a href="#intro">Intro</a></li>
    <li><a href="#problem">Problem</a></li>
    <li><a href="#model">Model</a></li>
    <li><a href="#implementation">Implementation</a></li>
    <li><a href="#demo">Live Demo</a></li>
  </ul>
  <div id="container">
    <div class="section" id="intro">
      <h1>Edge Covering</h1>
        <subtitle>with integer programming and Gurobi</subtitle>
    </div>

    <div class="section" id="problem">
      <h2><a href="#problem" name="problem">Problem Description</a></h2>
      Problem description goes here
    </div>
    <div class="section" id="model">
      <h2><a href="#model" name="model">Mathematical Model</a></h2>

      <p>Model description goes here.</p>

      <p>Let $V$ be the set of vertices in our graph and $E$ the set of edges.
      We are interested in computing an <i>edge cover</i>: a set of
      edges $C$ that cover all vertices in the graph (i.e. so that each vertex
      in the graph has at least one edge incident on it).
      </p>

      <p> A minimal edge cover is one that uses the fewest edges. We
        will compute this with integer programming. </p>

      <p>First we define the variables
      \[
      x_e = \left\{\begin{array}{ll}
             1 & \text{if  $e \in E$ is in the cover}\\
             0 & \mathrm{otherwise}
            \end{array}\right.
      \]
      </p>

      <p>Then the following model can be solved to obtain a minimal edge cover
      \[
      \begin{array}{ll}
      \text{minimize} & \sum_{e \in E} x_e \\
      \text{subject to} & \sum_{(u,v)=e \in E} x_e + \sum_{(v,u)=e \in E} x_e \ge 1, \quad \forall v \in V \\
                        & x_e \in \{ 0, 1 \} \quad \forall e \in E
      \end{array}
      \]
      </p>

      <p>Given an optimal solution $x^\star$ to the above model, we
      know that an edge $e$ will be in a minimal cover $C^\star$
      if $x^\star_e = 1$. </p>
    </div>
    <div class="section" id="implementation">
      <h2><a href="#implementation" name="implementation">Implementation</a></h2>
      <p>Below is the full implementation of the model (and the associated data) in
        Gurobi's Python interface:
      </p>
      <pre>
        from gurobipy import *

        vertices  = range(5)
        edges     = [(0, 1), (1, 2), (3, 4), (0, 2), (1, 3)]

        m = Model()
        edgeIn   = { v:[] for v in vertices }
        edgeOut  = { v:[] for v in vertices }
        edgeVars = {}

        for edge in edges:
           u = edge[0]
           v = edge[1]
           xe  = m.addVar(vtype=GRB.BINARY,obj=1.0, name="x_%d_%d" % (u,v))
           edgeVars[edge] = xe
           edgeOut[u] = edgeOut[u] + [xe]
           edgeIn[v] = edgeIn[v] + [xe]

        m.update()

        for v in vertices:
           m.addConstr(quicksum(edgeOut[v]) + quicksum(edgeIn[v]) >= 1, name="v%d" % v)

        m.optimize()
      </pre>
    </div>
    <div class="section" id="demo">
      <h2><a href="#demo" name="demo">Live Demo</a></h2>
      <div id="demoarea">
      </div>
      <button class="pure-button" onclick="compute()">Compute Edge Cover</button>
    </div>
    <div style="min-height:100px"></div>

<!--[if gt IE 8]><!--><script src="//ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script><!--<![endif]-->
<script src="http://davist11.github.io/jQuery-One-Page-Nav/jquery.nav.js"></script>
<script>
  $(document).ready(function() {
  console.log('calling onePageNav');
  $('#nav').onePageNav();
  });
</script>

<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<script>

var width = 960,
    height = 500;

var fill = d3.scale.category20();

var force = d3.layout.force()
    .size([width, height])
    .nodes([{}]) // initialize with a single node
    .linkDistance(30)
    .charge(-60)
    .on("tick", tick);

var svg = d3.select("#demoarea").append("svg")
    .attr("width", width)
    .attr("height", height)
    .on("mousemove", mousemove)
    .on("mousedown", mousedown);

svg.append("rect")
    .attr("width", width)
    .attr("height", height);

var nodes = force.nodes(),
    links = force.links(),
    node = svg.selectAll(".node"),
    link = svg.selectAll(".link");

var cursor = svg.append("circle")
    .attr("r", 30)
    .attr("transform", "translate(-100,-100)")
    .attr("class", "cursor");

restart();

function mousemove() {
  cursor.attr("transform", "translate(" + d3.mouse(this) + ")");
}

function mousedown() {
  var point = d3.mouse(this),
      node = {x: point[0], y: point[1]},
      n = nodes.push(node);

  // add links to any nearby nodes
  nodes.forEach(function(target) {
    var x = target.x - node.x,
        y = target.y - node.y;
    if (Math.sqrt(x * x + y * y) < 30) {
      links.push({source: node, target: target});
    }
  });

  restart();
}

function tick() {
  link.attr("x1", function(d) { return d.source.x; })
      .attr("y1", function(d) { return d.source.y; })
      .attr("x2", function(d) { return d.target.x; })
      .attr("y2", function(d) { return d.target.y; });

  node.attr("cx", function(d) { return d.x; })
      .attr("cy", function(d) { return d.y; });
}

function restart() {
  link = link.data(links);

  link.enter().insert("line", ".node")
      .attr("class", "link");

  node = node.data(nodes);

  node.enter().insert("circle", ".cursor")
      .attr("class", "node")
      .attr("r", 5)
      .call(force.drag);

  force.start();
}


function compute() {
  var vertices = [];
  var edges    = [];
  var edge;
  for (var i = 0; i < nodes.length; i++) {
     vertices.push(nodes[i].index);
  }
  for (i = 0; i < links.length; i++) {
     edge = links[i];
     if (edge.source.index !== edge.target.index) {
       edges.push([edge.source.index, edge.target.index]);
     }
  }
  console.log('vertices', vertices);
  console.log('edges', edges);

  d3.json('/edgecover')
    .header('Content-Type', 'application/json')
    .post(JSON.stringify({'vertices': vertices,
                          'edges': edges }), serverResponse);
}


function inArray (array, edge) {
  var u = edge[0];
  var v = edge[1];
  var bool = false;
  for (i = 0; i < array.length; i++) {
    edgeprime = array[i];
    if (u === edgeprime[0] && v === edgeprime[1]) {
      bool = true;
      break;
    }
  }
  return bool;
}


function serverResponse(error, data) {
   console.log('serverResponse');
   console.log('data', data);
   if (!error) {
      if ('cover' in data) {
        var cover = data.cover;
        console.log('cover', cover);
        d3.selectAll('.link') // execute function on each edge
        .each(function(d) {
                  var header = d3.select(this);
                  // Convert to array with the index as the number corresponding to a vertex
                  // (this also adds links (1,1), (2,2) etc but this will not affect cover
                  var d_arr = Object.keys(d).map(function (key) {return Number(d[key].index)});

                  if (inArray(cover, d_arr)) { // if edge is in cover color it red
                      header.style({'stroke': 'red'});
                      header.style({'stroke-width': 3});
                  } else {
                      header.style({'stroke': '#999'});
                      header.style({'stroke-width': 1});
                  }
        });
      }
   }
}

</script>
